/*
题目描述：圆圈中最后剩下的数字
0 ~ n - 1 排成一个圆圈，从数字 0 开始，每次从这个圆圈中删除第 m 个数字，求这个圆圈中剩下的最后一个数字
方法：
约瑟夫环问题，有两种解决办法：
1. 用环形链表模拟
2. 找出规律直接算
 */
public class E62 {
    public static void main(String[] args) {
        System.out.println(LastRemaining_Solution1(5, 3));
    }

    public static int LastRemaining_Solution(int n, int m) {
        if(n < 1 || m < 1){
            return -1;
        }
        int last = 0;
        for(int i = 2; i <= n; i++){
            last = (last + m) % i;
        }
        return last;
    }

    public static int LastRemaining_Solution1(int n, int m) {
        if(n == 0){
            return -1;
        }
        if(n == 1){
            return 0;
        }
        return (LastRemaining_Solution1(n - 1, m) + m) % n;
    }
    }
